package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_89_格雷编码 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_89_格雷编码().grayCode(1));
        System.out.println(new 力扣_89_格雷编码().grayCode(2));
        System.out.println(new 力扣_89_格雷编码().grayCode(3));
        System.out.println(new 力扣_89_格雷编码().grayCode(4));
    }

    /**
    题目：n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
     每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
     第一个整数是 0
     一个整数在序列中出现 不超过一次
     每对 相邻 整数的二进制表示 恰好一位不同 ，且
     第一个 和 最后一个 整数的二进制表示 恰好一位不同
     给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

     示例 1：
     输入：n = 2
     输出：[0,1,3,2]
     解释：
     [0,1,3,2] 的二进制表示是 [00,01,11,10] 。
     - 00 和 01 有一位不同
     - 01 和 11 有一位不同
     - 11 和 10 有一位不同
     - 10 和 00 有一位不同
     [0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
     - 00 和 10 有一位不同
     - 10 和 11 有一位不同
     - 11 和 01 有一位不同
     - 01 和 00 有一位不同

     示例 2：
     输入：n = 1
     输出：[0,1]

    分析：【R ♥♥♥♥】
       1.回溯法: 年轻人阿，要学会画树图。 -- 执行用时：2 ms, 在所有 Java 提交中击败了99.54%的用户
        a.相同1的个数，再放置1个1时，放置的位置不断遍历 eg: [001,      010,  100]
                                                          [101,011]   [110]
                                                              [111]
        b。利用位运算，移动1的位置:current+(1<<i);

    边界值 & 注意点：
       1.
     **/
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        getnext(0,0,n,res);
        return res;
    }

    /**
     * Description: 回溯获取下一个值
     * @param current 当前的值
     * @param index 当前开始加2的n次方开始值
     * @param n  总位数
     * @param res 返回集合
     */
    private void getnext(int current,int index,int n, List<Integer> res) {
        if(n==index) return;
        for (int i = index; i < n; i++) {
            int numb = current+(1<<i);
            res.add(numb);
            getnext(numb,i+1,n,res);
        }
    }
}
